package com.hy.stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class IsValid {


    /**
     * 栈与队列：系统中处处都是栈的应用
     *20. 有效的括号
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 注意空字符串可被认为是有效字符串。
     *
     * 示例 2:
     * 输入: "()[]{}"
     * 输出: true
     * 思路
     * 由于栈结构的特殊性，非常适合做对称匹配类的题目。
     *
     * 首先要弄清楚，字符串里的括号不匹配有几种情况。
     *
     * 一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。
     *
     * 建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。
     *
     * 先来分析一下 这里有三种不匹配的情况，
     *
     * 1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。   ([]{}()
     * 2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。   ([{}}}
     * 3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。    ()[{}]))
     *
     * @return
     */


    public static boolean isValid(String s){
        Deque<Character> deque = new LinkedList<>();
        char ch ;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '('){
                deque.push(')');
            }else if (ch == '['){
                deque.push(']');
            }else if (ch == '{'){
                deque.push('}');
            }else if (deque.isEmpty() || deque.peek() != ch){
                return false;
            }else {
                //如果是右括号判断是否和栈顶元素匹配    弹出元素
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配  是否为空(为空元素按顺序弹出 则匹配成功)
        return deque.isEmpty();
    }


    public static void main(String[] args) {
        String s = "([]{}()";
        System.out.println("res: "+isValid(s));
    }
}
